GermanWikipedia - /page/entry.mu

Micron Document

<!DOCTYPE html>

<title>Shortest-Job-Next</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Shortest-Job-Next</span></h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p><b>Shortest-Job-Next</b> (SJN) oder <b>Shortest-Job-First</b> (SJF) ist ein <a href="Scheduling#Präemptive_und_nicht-präemptive_Verfahren" title="Scheduling">nonpräemptives</a> <a href="Prozess-Scheduler" title="Prozess-Scheduler">Scheduling</a>-Verfahren, das eingesetzt wird, um rechenwillige <a href="Thread_(Informatik)" title="Thread (Informatik)">Threads</a> oder/und <a href="Prozess_(Informatik)" title="Prozess (Informatik)">Prozesse</a> auf die physischen <a href="Prozessor" title="Prozessor">Prozessoren</a> des <a href="Computer" title="Computer">Rechners</a> zu verteilen.<sup id="cite_ref-ostep-1_1-0" class="reference"><a href="#cite_note-ostep-1-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p><p>Abwandlungen dieses Scheduling-Verfahrens sind

</p>

<ul><li>Shortest-Processing-Time (<b>SPT</b>) auch bekannt als Shortest-Remaining-Time-Next (<b>SRTN</b>)</li></ul>

<dl><dd><dl><dd>Dabei handelt es sich um eine <a href="Scheduling#Präemptive_und_nicht-präemptive_Verfahren" title="Scheduling">präemptive</a> Version von SJF</dd></dl></dd></dl>

<ul><li>Shortest-Process-Next (<b>SPN</b>)</li></ul>

<dl><dd><dl><dd>Für interaktive Prozesse</dd></dl></dd></dl>

<p>Die Grundlage des SJF-Verfahrens ist eine Rangliste, ähnlich dem <a href="First_In_%E2%80%93_First_Out" title="First In – First Out">FIFO</a>-Verfahren. Hierbei wird die Länge des CPU-Bursts (Rechenzeit) zur Bestimmung der Rangfolge herangezogen. Threads mit einer kurzen Burstlänge werden den längeren vorgezogen. Folglich kann es zu dem Problem führen, dass ein Thread mit einem langen CPU-Burst fast nie zum Zuge kommt. Allerdings stößt man leicht auf derartige Probleme, sobald man Prioritäten bildet.

Sind mehrere CPU-Bursts gleich lang, kommt es dem <a href="First_In_%E2%80%93_First_Out" title="First In – First Out">FCFS</a>-Verfahren gleich.

</p><p>Gegenüber dem FCFS-Verfahren hat SJF den Vorteil, dass es den nachteiligen Konvoi-Effekt vermeidet. Weiterhin lässt es sich beweisen, dass SJF die Wartezeit auf ein Optimum bringt.

Demgegenüber steht der große Nachteil, dass das Verfahren praktisch nicht implementierbar ist, da die CPU-Burstlängen in der Regel unbekannt sind. Allerdings sind näherungsweise Implementierungen möglich.

</p><p>Hinter der Approximation des SJF Verfahrens steckt eine simple Idee. Da die Länge des künftigen CPU-Bursts nicht bekannt ist, kann man beobachten, wie sich ein Thread in der Vergangenheit verhalten hat, in der Hoffnung, er wird sich in der Zukunft ähnlich verhalten.

</p><p>Dabei ist Burst<sub>geschätzt</sub>(<i>n</i> + 1) = α · Burst<sub>gemessen</sub>(<i>n</i>) + (1 − α) · Burst<sub>geschätzt</sub>(<i>n</i>)

Mit der Veränderlichen α lässt sich die Gewichtung der vergangenen Messungen festlegen. Werte nahe der 1 weisen der Vergangenheit einen geringen Stellenwert zu.

</p><p>SJF lässt sich <a href="Pr%C3%A4emptives_Multitasking" class="mw-redirect" title="Präemptives Multitasking">präemptiv</a> (dieser <a href="Algorithmus" title="Algorithmus">Algorithmus</a> wird Shortest Remaining Time Next genannt) und nicht-präemptiv <a href="Implementierung" title="Implementierung">implementieren</a>. Wobei bei der nicht-präemptiven Implementierung der Threadwechsel erst nach einer freiwilligen Abgabe durch den Thread selber oder nach einer blockierenden Operation (z. B. E/A) bzw. durch Ablauf der Lebensbedingung des Threads oder/und Prozesses stattfindet. D. h., es findet keine automatische Unterbrechung wie z. B. bei <a href="Round_Robin_(Informatik)" title="Round Robin (Informatik)">Round-Robin</a>-Verfahren statt.

</p><p>SJF kann auch für interaktive Prozesse abgewandelt werden. Man spricht dann vom Shortest-Process-Next. Als Alternative gibt es das präemptive Shortest-Remaing-Time, das auf Shortest-Process-Next basiert.

</p>

<div class="mw-heading mw-heading2"><h2 id="Beispiel">Beispiel</h2></div>

<table>

<td>Prozess

</td>

<td>Ankunftszeit

</td>

<td>Dauer

</td></tr>

<tr>

<td>A

</td>

<td>0

</td>

<td>4

</td></tr>

<tr>

<td>B

</td>

<td>2

</td>

<td>7

</td></tr>

<tr>

<td>C

</td>

<td>3

</td>

<td>6

</td></tr>

<tr>

<td>D

</td>

<td>9

</td>

<td>2

</td></tr>

<tr>

<td>E

</td>

<td>16

</td>

<td>1

</td></tr></tbody></table>

<p>Beim

fünften Abarbeitungsschritt ist Prozess A abgeschlossen und es stehen Prozess B und C zur Auswahl bereit. Da C nur 6

Schritte, B jedoch 7 Schritte zur Fertigstellung benötigt, wird C

zuerst ausgeführt.

</p><p>Zu Zeitpunkt 11 wird der nur 2 Schritte lange Prozess D dem 7 Schritte Prozess B vorgezogen.

</p><p>Zu Zeitpunkt 13 sind Prozesse A, C und D abgearbeitet. Prozess E gibt es noch nicht, so dass Prozess B ausgeführt werden kann.

</p>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-ostep-1-1"><span class="mw-cite-backlink"><a href="#cite_ref-ostep-1_1-0">↑</a></span> <span class="reference-text"><span class="cite">Remzi H. Arpaci-Dusseau, Andrea C. Arpaci-Dusseau: <a rel="nofollow" class="external text" href="https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf"><i>Operating Systems: Three Easy Pieces.</i></a> (PDF; 116 kB) Arpaci-Dusseau Books, 2014,<span class="Abrufdatum"> abgerufen am 9. Januar 2021</span>.</span><span style="display: none;" class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rfr_id=info%3Asid%2Fde.wikipedia.org%3AShortest-Job-Next&rft.title=Operating+Systems%3A+Three+Easy+Pieces&rft.description=Operating+Systems%3A+Three+Easy+Pieces&rft.identifier=https%3A%2F%2Fpages.cs.wisc.edu%2F%7Eremzi%2FOSTEP%2Fcpu-sched.pdf&rft.creator=Remzi+H.+Arpaci-Dusseau%2C+Andrea+C.+Arpaci-Dusseau&rft.publisher=Arpaci-Dusseau+Books&rft.date=2014"> </span></span>

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-10-13" href="https://de.wikipedia.org/wiki/?title=Shortest-Job-Next&oldid=260565526">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>